1. Field of the Invention
The present invention generally relates to data processing systems, and more particularly to a method of allocating resources in a data array such as a cache memory.
2. Description of the Related Art
Computer systems employ a variety of optimization techniques to more efficiently utilize data resources. For example, data arrays such as cache memory use special allocation methods to temporarily store data in a limited number of entries. When all of the entries in a cache memory are full (i.e., there are no unused or available entries), and the cache system receives a request to store a new data value, it must decide which of the old data values already stored in the cache memory must be replaced (overwritten). This allocation process is known as eviction.
The eviction process applies to many other types of resources and systems, but cache memories in particular are very useful for understanding general eviction-related concepts. Cache memories generally fall into one of three types: set associative, fully associative, or direct mapped. In a set associative cache, the cache entries are divided into groups referred to as sets. A set is the collection of cache entries that a given memory block can reside in, according to preset mapping functions. The number of entries in a set is referred to as the associativity of the cache, e.g., a 2-way set associative cache means that, for any given memory block, there are two blocks in the cache that the memory block can be mapped into; however, several different blocks in main memory can be mapped to any given set. A 1-way set associative cache is direct mapped, that is, there is only one cache block that can contain a particular memory block. A cache is said to be fully associative if a memory block can occupy any cache entry, i.e., there is one set, and the address tag for the cache entry is the full address of the memory block.
Fully associative cache memories often consist of a content addressable memory (CAM) storing the memory addresses and a random-access memory (RAM) storing the memory values, that is, operand data or program instructions. CAMs typically consist of rows and columns of memory cells generally similar to RAM cells providing read and write functions but additional circuitry is provided to permit matching. During a search operation an input to the CAM represents a memory address and the CAM compares the input with the addresses held in the CAM to see whether or not a match occurs. When a match is found an output signal is provided to a corresponding location in the data RAM so that a read or write operation may take place with the corresponding location in the data RAM of the cache. The cells of the CAM are arranged so that each row of cells holds a memory address, and each row of cells is connected by a match line to a corresponding word line of the data RAM to enable access of that word line when a match occurs on that match line.
When all of the entries in a given set are full and the cache receives a request, whether a read operation or a write operation, to a memory location that maps into the full set, the cache must evict one of the blocks currently in that set. While an entry can simply be randomly selected for eviction, this approach leads to inefficient cache usage, so system designers typically employ more sophisticated techniques to optimize the eviction process. One common technique having many variations is generally referred to as “least recently used,” or LRU. LRU algorithms proceed on the assumption that the oldest entry in the cache or other data array is the entry which most likely will not be used in the near future by the particular program running at that time. Once the system identifies the entry in the set which is the least recently used, it allocates this region for the new store operation.